1. Field of the Invention
The present invention generally relates to logic circuits for computational devices, and more particularly to a barrel shifter or rotator.
2. Description of the Related Art
A shifter, or rotator, is a combinational logic circuit that can shift an operand data value by a specified number of places (bits), i.e., move the bits left or right within the data field. Shifters are useful for many computational applications including arithmetic operations, address generation, variable-length coding, and bit indexing, and have become essential to modern integrated circuit devices such as digital signal processors and general-purpose microprocessors.
In the simplest shifter circuit, each bit is incrementally shifted one place at a time, so shifting data by n bits would require n clock cycles. This delay is unacceptable for conventional systems having, e.g., 64-bit or 128-bit data values, so an improved design known as a barrel shifter has been devised which can shift long-bit values in a single clock cycle. Barrel shifters basically trade chip area of the integrated circuit (number of gates) for speed. A barrel shifter relies on a large number of cascaded multiplexers. The minimum number of 2:1 multiplexers required for an n-bit word is n log2 n; for example, a 64-bit barrel shifter requires 384 multiplexers. One common usage of a barrel shifter is in the hardware implementation of floating-point arithmetic. For a floating-point add or subtract operation, the significands of the two numbers must be aligned, which requires shifting the smaller number to the right and increasing its exponent until it matches the exponent of the larger number. This operation is conveniently accomplished by subtracting the exponents, and using the barrel shifter to shift the smaller number to the right by that difference, in one cycle.
FIG. 1 shows the basic structure of a conventional 64-bit barrel shifter 10. A set of input latches 12 are used to store the operand data and the shift control data for the next shift operation. The shift control data includes a one-bit shift direction signal (shift_right) and a six-bit shift amount signal (shift_amount<0:5>) representing a shift of 0-63 places. The operand data is passed to a formatter and driver 14 which may perform formatting of the data for the multiplexer cascade, and the shift control data is passed to an invert with shift right circuit 16 which generates decoder signals that are later decoded to control the multiplexers. In this design, the multiplexer cascade has two stages wherein an intermediate or coarsely-shifted value (the operand data shifted by some integer multiple of 8) is selected by a first selector 18, and then a fully shifted value (further shifted by 0-7) is selected by a second selector 20 using the output of selector 18. Selector 18 selects one group out of eight groups, each having 72 bits, while selector 20 selects one group out of nine groups, each having 64 bits, due to the encoding inherent in the use of invert with shift right circuit 16. The first set of groups have an extra 8 wrap-around bits appended to the operand data to avoid the data transfer delay penalty incurred by long wiring that would otherwise be required. Invert with shift right circuit 16 generates a decode signal which may be considered as having two halves, a most-significant bit (MSB) half and a least significant bit (LSB) half. The MSB decode bits are used to derive the first selection signal and the LSB decode bits are used to derive the second selection signal, along with the shift_right signal. A first decoder 22 computes the selection signal for selector 18, and a second decoder 24 computes the selection signal for selector 20. Decoder 22 is a three-to-eight decoder, i.e., it receives a 3-bit input and computes an 8-bit output. While decoder 24 may be considered a three-to-nine decoder because it receives a 3-bit input and computes a 9-bit output, it also requires the shift_right input so it is designated as a four-to-nine decoder in FIG. 1. The 64-bit output of selector 20 (raw shifted data) can be further used as an input to a multiplexer and driver 26 to generate final shifted data that is then stored in output latches 28.